Termination w.r.t. Q proof of TRS/Rubiowst99.trs

Termination w.r.t. Q of the following Term Rewriting System could be proven:

Q restricted rewrite system:
The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

Q is empty.

↳ QTRS

  ↳ Overlay + Local Confluence

Q restricted rewrite system:
The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

Q is empty.

The TRS is overlay and locally confluent. By [15] we can switch to innermost.

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

Q restricted rewrite system:
The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

Using Dependency Pairs [1,13] we result in the following initial DP problem:
Q DP problem:
The TRS P consists of the following rules:

U41(dout(DX), X) → U42(din(der(DX)), X, DX)
U21(dout(DX), X, Y) → DIN(der(Y))
DIN(der(plus(X, Y))) → U21(din(der(X)), X, Y)
DIN(der(der(X))) → DIN(der(X))
DIN(der(times(X, Y))) → DIN(der(X))
U31(dout(DX), X, Y) → U32(din(der(Y)), X, Y, DX)
DIN(der(plus(X, Y))) → DIN(der(X))
DIN(der(times(X, Y))) → U31(din(der(X)), X, Y)
U21(dout(DX), X, Y) → U22(din(der(Y)), X, Y, DX)
U41(dout(DX), X) → DIN(der(DX))
U31(dout(DX), X, Y) → DIN(der(Y))
DIN(der(der(X))) → U41(din(der(X)), X)

The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

Q DP problem:
The TRS P consists of the following rules:

U41(dout(DX), X) → U42(din(der(DX)), X, DX)
U21(dout(DX), X, Y) → DIN(der(Y))
DIN(der(plus(X, Y))) → U21(din(der(X)), X, Y)
DIN(der(der(X))) → DIN(der(X))
DIN(der(times(X, Y))) → DIN(der(X))
U31(dout(DX), X, Y) → U32(din(der(Y)), X, Y, DX)
DIN(der(plus(X, Y))) → DIN(der(X))
DIN(der(times(X, Y))) → U31(din(der(X)), X, Y)
U21(dout(DX), X, Y) → U22(din(der(Y)), X, Y, DX)
U41(dout(DX), X) → DIN(der(DX))
U31(dout(DX), X, Y) → DIN(der(Y))
DIN(der(der(X))) → U41(din(der(X)), X)

The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.
We deleted some edges using various graph approximations

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

            ↳ QDP

              ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

U21(dout(DX), X, Y) → DIN(der(Y))
DIN(der(der(X))) → DIN(der(X))
DIN(der(times(X, Y))) → U31(din(der(X)), X, Y)
U31(dout(DX), X, Y) → DIN(der(Y))
U41(dout(DX), X) → DIN(der(DX))
DIN(der(der(X))) → U41(din(der(X)), X)
U41(dout(DX), X) → U42(din(der(DX)), X, DX)
DIN(der(plus(X, Y))) → U21(din(der(X)), X, Y)
DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(plus(X, Y))) → DIN(der(X))
U31(dout(DX), X, Y) → U32(din(der(Y)), X, Y, DX)
U21(dout(DX), X, Y) → U22(din(der(Y)), X, Y, DX)

The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [13,14,18] contains 1 SCC with 3 less nodes.

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ QDP

                  ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

DIN(der(plus(X, Y))) → U21(din(der(X)), X, Y)
U21(dout(DX), X, Y) → DIN(der(Y))
DIN(der(der(X))) → DIN(der(X))
DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(plus(X, Y))) → DIN(der(X))
DIN(der(times(X, Y))) → U31(din(der(X)), X, Y)
U41(dout(DX), X) → DIN(der(DX))
U31(dout(DX), X, Y) → DIN(der(Y))
DIN(der(der(X))) → U41(din(der(X)), X)

The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

DIN(der(times(X, Y))) → U31(din(der(X)), X, Y)
U41(dout(DX), X) → DIN(der(DX))
U31(dout(DX), X, Y) → DIN(der(Y))
DIN(der(der(X))) → U41(din(der(X)), X)

The remaining pairs can at least be oriented weakly.

DIN(der(plus(X, Y))) → U21(din(der(X)), X, Y)
U21(dout(DX), X, Y) → DIN(der(Y))
DIN(der(der(X))) → DIN(der(X))
DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(plus(X, Y))) → DIN(der(X))

Used ordering: Combined order from the following AFS and order.
DIN(x1) = x1
der(x1) = der
plus(x1, x2) = x1
U21(x1, x2, x3) = U21
din(x1) = din
dout(x1) = dout(x1)
times(x1, x2) = x2
U31(x1, x2, x3) = x1
U41(x1, x2) = U41(x1)
u21(x1, x2, x3) = x1
u22(x1, x2, x3, x4) = u22(x4)
u32(x1, x2, x3, x4) = x1
u41(x1, x2) = x1
u42(x1, x2, x3) = u42(x1)
u31(x1, x2, x3) = x1

Lexicographic path order with status [19].
Quasi-Precedence:

[dout₁, u22₁, u42_1] > [der, U21] > U41₁ > din

Status:

u22₁: [1]
U41₁: [1]
der: []
din: []
U21: []
u42₁: [1]
dout₁: [1]

The following usable rules [14] were oriented:

u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(der(X))) → u41(din(der(X)), X)
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u42(dout(DDX), X, DX) → dout(DDX)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ QDP

                  ↳ QDPOrderProof

                    ↳ QDP

                      ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

U21(dout(DX), X, Y) → DIN(der(Y))
DIN(der(plus(X, Y))) → U21(din(der(X)), X, Y)
DIN(der(der(X))) → DIN(der(X))
DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(plus(X, Y))) → DIN(der(X))

The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

U21(dout(DX), X, Y) → DIN(der(Y))
DIN(der(plus(X, Y))) → U21(din(der(X)), X, Y)
DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(plus(X, Y))) → DIN(der(X))

The remaining pairs can at least be oriented weakly.

DIN(der(der(X))) → DIN(der(X))

Used ordering: Combined order from the following AFS and order.
U21(x1, x2, x3) = U21(x2, x3)
dout(x1) = dout
DIN(x1) = x1
der(x1) = x1
plus(x1, x2) = plus(x1, x2)
din(x1) = din(x1)
times(x1, x2) = times(x1)
u21(x1, x2, x3) = x1
u22(x1, x2, x3, x4) = u22(x2, x3, x4)
u32(x1, x2, x3, x4) = u32(x1, x2, x3, x4)
u41(x1, x2) = u41(x1, x2)
u42(x1, x2, x3) = u42(x1, x2)
u31(x1, x2, x3) = u31(x2, x3)

Lexicographic path order with status [19].
Quasi-Precedence:

plus₂ > U21₂ > [dout, times₁, u22_3]
plus₂ > din₁ > [dout, times₁, u22_3]
u41₂ > din₁ > [dout, times₁, u22_3]
u41₂ > u42₂ > [dout, times₁, u22_3]
u31₂ > din₁ > [dout, times₁, u22_3]
u31₂ > u32₄ > [dout, times₁, u22_3]

Status:

U21₂: [1,2]
u22₃: [3,2,1]
u41₂: [2,1]
plus₂: [1,2]
din₁: [1]
u32₄: [1,3,2,4]
dout: []
times₁: [1]
u42₂: [2,1]
u31₂: [2,1]

The following usable rules [14] were oriented: none

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ QDP

                  ↳ QDPOrderProof

                    ↳ QDP

                      ↳ QDPOrderProof

                        ↳ QDP

                          ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

DIN(der(der(X))) → DIN(der(X))

The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

DIN(der(der(X))) → DIN(der(X))

The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
DIN(x1) = DIN(x1)
der(x1) = der(x1)

Lexicographic path order with status [19].
Quasi-Precedence:

[DIN₁, der_1]

Status:

DIN₁: [1]
der₁: [1]

The following usable rules [14] were oriented: none

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ QDP

                  ↳ QDPOrderProof

                    ↳ QDP

                      ↳ QDPOrderProof

                        ↳ QDP

                          ↳ QDPOrderProof

                            ↳ QDP

                              ↳ PisEmptyProof

Q DP problem:
P is empty.
The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.